
'''
https://programmercarl.com/0454.%E5%9B%9B%E6%95%B0%E7%9B%B8%E5%8A%A0II.html#%E7%AE%97%E6%B3%95%E5%85%AC%E5%BC%80%E8%AF%BE
https://leetcode.cn/problems/4sum-ii/description/
四数相加，求集合个数
a [1,2]
b [-2,-1]
c [-1,2]
d [0,2]
组成0的集合个数为2  [0,0,0,1][1,1,0,0]
key(a+b) value(排列组合个数）
-1       1   （1+ -2 = -1）
0        2  （1+ -1 = 0，2+ -2 =0共2个排列）
1        1   （2+ -1 = 1）

只要 0 - (c+d) 在key中存在（相当于a+b+c+d=0，那value就是集合排列个数)
'''

def l454(nums1,nums2,nums3,nums4):
    from collections import defaultdict
    # 构建 key value 默认为0，若默认为123，可写成defaultdict(lambda:123)
    d = defaultdict(int)
    res = 0
    for i in nums1:
        for j in nums2:
            d[i+j] += 1
    for i in nums3:
        for j in nums4:
            res += d[0-i-j]
    return res
    pass

if __name__ == '__main__':
    print(l454([1,2],[-2,-1],[-1,2],[0,2]))
    # print(l1([3,2,4],6))
    # print(l1([3,3],6))
    # print(l1([6,4],6))

    pass